{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Palindrome III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证回文字符串 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个字符串&nbsp;<code>s</code>&nbsp;和一个整数&nbsp;<code>k</code>，若这个字符串是一个「k&nbsp;<strong>回文</strong>&nbsp;」，则返回 <code>true</code> 。</p>\n",
    "\n",
    "<p>如果可以通过从字符串中删去最多 <code>k</code> 个字符将其转换为回文，那么这个字符串就是一个「<strong>k</strong>&nbsp;<strong>回文</strong>&nbsp;」。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcdeca\", k = 2\n",
    "<strong>输</strong><strong>出：</strong>true\n",
    "<strong>解释：</strong>删去字符 “b” 和 “e”。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abbababa\", k = 1\n",
    "<strong>输</strong><strong>出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code>&nbsp;中只含有小写英文字母</li>\n",
    "\t<li><code>1 &lt;= k&nbsp;&lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-palindrome-iii](https://leetcode.cn/problems/valid-palindrome-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-palindrome-iii](https://leetcode.cn/problems/valid-palindrome-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcdeca\"\\n2', '\"abbababa\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        for i in range(len(s), -1, -1):\n",
    "            prev = 0\n",
    "            for j in range(i+1, n):\n",
    "                nprev = dp[j]\n",
    "                if s[i]==s[j]:\n",
    "                    dp[j] = prev\n",
    "                else:\n",
    "                    dp[j]=1+min(dp[j], dp[j-1])\n",
    "                prev = nprev\n",
    "        return dp[-1]<=k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [0 for _end in range(len(s))] \n",
    "\n",
    "        for start in range(len(s) - 1, -1, -1):\n",
    "            prev = 0\n",
    "            for end in range(start + 1, len(s)):\n",
    "                temp = validStat[end]\n",
    "\n",
    "                if s[start] == s[end]:\n",
    "                    validStat[end] = prev\n",
    "                else:\n",
    "                    validStat[end] = min(validStat[end], validStat[end - 1]) + 1\n",
    "                prev = temp\n",
    "        minK = validStat[len(s) - 1]\n",
    "        return minK <= k\n",
    "\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是k回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1):\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1])\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是k回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1):\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1])\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     # 区间i,j 能否在k宽容度下成为palindrome\n",
    "        #     if j-i+1 <= k:\n",
    "        #         return True\n",
    "        #     elif k == -1:\n",
    "        #         return False\n",
    "            \n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1,k)\n",
    "            \n",
    "        #     return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        # return dfs(0,n-1,k)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     # to make ij palindrome, minimal k\n",
    "        #     if i >= j:\n",
    "        #         return 0\n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1)\n",
    "        #     return min(dfs(i+1,j), dfs(i,j-1))+1\n",
    "        # return dfs(0,n-1) <= k\n",
    "\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j-1, -1, -1):\n",
    "                # [i,j]\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1]\n",
    "                else:\n",
    "                    f[i][j] = min(f[i+1][j], f[i][j-1])+1\n",
    "        return f[0][n-1] <= k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        if len(s) <= k:\n",
    "            return True\n",
    "\n",
    "        # dp[i][j]: longest palindrome length within [i, j]\n",
    "        dp = [[0] * len(s) for _ in range(len(s))]\n",
    "\n",
    "        for j in range(0, len(s)):\n",
    "            dp[j][j] = 1\n",
    "            for i in reversed(range(j)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        return len(s) - dp[0][-1] <= k\n",
    "\n",
    "\n",
    "#  a (a) b a a b (a) b b a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[0 for j in range(n)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])\n",
    "        return len(s) - dp[0][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n=len(s)\n",
    "        dp=[[0 for _ in range(n)] for _ in range(n)]\n",
    "        if 1+k>=n:\n",
    "            return True\n",
    "        for l in range(n-2,-1,-1):\n",
    "            dp[l][l]=1\n",
    "            for r in range(l+1,n):\n",
    "                if s[l]==s[r]:\n",
    "                    dp[l][r]=dp[l+1][r-1]+2\n",
    "                else:\n",
    "                    dp[l][r]=max(dp[l+1][r],dp[l][r-1])\n",
    "                if dp[l][r]+k>=n:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [[0 for _end in range(len(s))] for _start in range(len(s))]\n",
    "        for start in range(len(s) - 1, -1, -1):\n",
    "            for end in range(start + 1, len(s)):\n",
    "                if s[start] == s[end]:\n",
    "                    validStat[start][end] = validStat[start + 1][end - 1]\n",
    "                else:\n",
    "                    validStat[start][end] = min(validStat[start + 1][end], validStat[start][end - 1]) + 1\n",
    "        \n",
    "        minK = validStat[0][len(s) - 1]\n",
    "        return minK <= k\n",
    "\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 是x回文\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1) # 删掉1个数（2种位置），k+1\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j-1]) # 端点相同，可以不删，也可以删（取k最小）\n",
    "        \n",
    "        return dp[0][n-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        #最长回文子序列.\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]  #每个字母自己。都是一个长度为1的回文串\n",
    "\n",
    "        if 1 + k >= n:\n",
    "            return True\n",
    "\n",
    "        for l in range(n-2, -1, -1):    #l依赖于l+1\n",
    "            dp[l][l] = 1            \n",
    "            for r in range(l + 1, n):   #r依赖于r-1\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l+1][r-1] + 2\n",
    "                else:\n",
    "                    dp[l][r] = max(dp[l+1][r], dp[l][r-1])\n",
    "                \n",
    "                if dp[l][r] + k >= n:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [ [0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i+1, n, 1):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])\n",
    "        return dp[0][n-1] + k >= len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        t = s[::-1]\n",
    "        l = len(s)\n",
    "\n",
    "        dp = [[0] * (l + 1) for _ in range(l + 1)]\n",
    "\n",
    "        for i in range(1, l + 1):\n",
    "            for j in range(1, l + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        \n",
    "        return (l - dp[l][l]) <= k\n",
    "\n",
    "\n",
    "    # def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "    #     l = len(s)\n",
    "    #     dp = [[[True if i == j else False] * (k + 1) for j in range(l + 1)] for i in range(l + 1)]\n",
    "\n",
    "    #     def isPalindrome(word):\n",
    "    #         l = len(word) // 2\n",
    "    #         for i in range(l):\n",
    "    #             if word[i] != word[len(word) - 1 - i]:\n",
    "    #                 return False\n",
    "    #         return True\n",
    "\n",
    "    #     for i in range(l, 0, -1):\n",
    "    #         for j in range(i, l + 1):\n",
    "    #             for t in range(k + 1):\n",
    "    #                 max_len = j - i + 1\n",
    "    #                 if t > max_len:\n",
    "    #                     dp[i][j][t] = True\n",
    "    #                     continue\n",
    "    #                 if t == 0:\n",
    "    #                     word = s[i - 1:j + 1 - 1]\n",
    "    #                     dp[i][j][t] = isPalindrome(word)\n",
    "    #                 else:\n",
    "    #                     if i == j:\n",
    "    #                         continue\n",
    "    #                     if s[i - 1] == s[j - 1]:\n",
    "    #                         dp[i][j][t] = dp[i + 1][j - 1][t]\n",
    "    #                     else:\n",
    "    #                         dp[i][j][t] = dp[i][j - 1][t - 1] or dp[i + 1][j][t - 1]\n",
    "    #     return dp[1][l][k]\n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if j - i < 1:\n",
    "                    f[i][j] = 0\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        f[i][j] = f[i + 1][j - 1]\n",
    "                    else:\n",
    "                        f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1\n",
    "        return f[0][n - 1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        #最长回文子序列.\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]  #每个字母自己。都是一个长度为1的回文串\n",
    "\n",
    "        if 1 + k >= n:\n",
    "            return True\n",
    "\n",
    "        for l in range(n-2, -1, -1):    #l依赖于l+1\n",
    "            dp[l][l] = 1            \n",
    "            for r in range(l + 1, n):   #r依赖于r-1\n",
    "                if s[l] == s[r]:\n",
    "                    dp[l][r] = dp[l+1][r-1] + 2\n",
    "                else:\n",
    "                    dp[l][r] = max(dp[l+1][r], dp[l][r-1])\n",
    "                \n",
    "                if dp[l][r] + k >= n:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = i+l-1\n",
    "                if j >= n: break\n",
    "                if s[i] == s[j]:\n",
    "                    if l == 2:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                else:\n",
    "                    if l == 2:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "        return dp[0][-1] <= k\n",
    "\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def isValid(left, right, k):\n",
    "        #     while left < right:\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #             right -= 1\n",
    "        #         else:\n",
    "        #             if k > 0:\n",
    "        #                 k -= 1\n",
    "        #                 return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "        #             else:\n",
    "        #                 return False\n",
    "        #     return True \n",
    "        # return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "\n",
    "        return dp[0][-1] + k >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        re_s = \"\".join(list(s)[::-1] )\n",
    "        lens = len(s)\n",
    "        dp = [[0 for _ in range(lens+1)]for _ in range(lens+1)]\n",
    "\n",
    "        for i in range(1, lens+1):\n",
    "            for j in range(1, lens+1):\n",
    "                if s[i-1] == re_s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return lens-dp[-1][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        reversed_s = s[::-1]\n",
    "        n = len(s)\n",
    "        \n",
    "        # Initialize a dp array\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        \n",
    "        # Fill the dp array\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                if s[i-1] == reversed_s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        # If the length of s minus the value in the bottom-right corner of the dp array (i.e., the length of LCS) \n",
    "        # is less than or equal to k, then it's a valid palindrome.\n",
    "        return n - dp[n][n] <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        t = s[::-1]\n",
    "        n = len(s)\n",
    "        dp = [[0 for j in range(n + 1)] for i in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        return n - dp[-1][-1] <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 0\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = i+l-1\n",
    "                if j >= n: break\n",
    "                if l == 2:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "                # if s[i] == s[j]:\n",
    "                #     if l == 2:\n",
    "                #         dp[i][j] = 0\n",
    "                #     else:\n",
    "                #         dp[i][j] = dp[i+1][j-1]\n",
    "                # else:\n",
    "                #     if l == 2:\n",
    "                #         dp[i][j] = 1\n",
    "                #     else:\n",
    "                #         dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1\n",
    "        print(dp)\n",
    "        return dp[0][-1] <= k\n",
    "\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def isValid(left, right, k):\n",
    "        #     while left < right:\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #             right -= 1\n",
    "        #         else:\n",
    "        #             if k > 0:\n",
    "        #                 k -= 1\n",
    "        #                 return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "        #             else:\n",
    "        #                 return False\n",
    "        #     return True \n",
    "        # return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        validStat = [[-1 for _end in range(len(s))] for _start in range(len(s))]\n",
    "\n",
    "        def _solve(start, end):\n",
    "            if start >= end:\n",
    "                validStat[start][end] = 0\n",
    "                return validStat[start][end]\n",
    "            if start == end - 1:\n",
    "                validStat[start][end] = 0 if s[start] == s[end] else 1\n",
    "                return  validStat[start][end]\n",
    "            if validStat[start][end] != -1:\n",
    "                return validStat[start][end]\n",
    "            \n",
    "            if s[start] == s[end]:\n",
    "                validStat[start][end] = _solve(start + 1, end - 1)\n",
    "                return validStat[start][end]\n",
    "            else:\n",
    "                validStat[start][end] = min(_solve(start, end - 1), _solve(start + 1, end)) + 1\n",
    "                return validStat[start][end]\n",
    "\n",
    "        minK = _solve(0, len(s) - 1)\n",
    "        \n",
    "        return minK <= k    \n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        n = len(s)\n",
    "        def dfs(i, j): # longest palindrome subsequence\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if i > j:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if s[i] == s[j]:\n",
    "                res = max(res, dfs(i+1, j-1) + 2)\n",
    "            else:\n",
    "                res = max(res, dfs(i+1, j), dfs(i, j-1))\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        return dfs(0, n-1) >= n -k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i >j :\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i +1, j -1) + 2\n",
    "            else:\n",
    "                res = max(dfs(i +1, j), dfs(i, j-1))\n",
    "            memo[(i, j)] = res\n",
    "            return memo[(i, j)]\n",
    "        return len(s) - dfs(0, len(s) -1) <= k\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        memo = {}\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                res = dfs(i +1, j -1) + 2\n",
    "            else:\n",
    "                x = dfs(i +1, j)\n",
    "                y = dfs(i, j -1)\n",
    "                # res = max(res, x, y) # wrong: reference before assign \n",
    "                res = max(x, y)\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "        n = len(s)\n",
    "        res = dfs(0, n -1)\n",
    "        return n - res <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        a = s\n",
    "        n = len(a)\n",
    "        @cache \n",
    "        def f(i, j):\n",
    "            if i==j:\n",
    "                return 1 \n",
    "            else:\n",
    "                if j<i:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    if a[i]==a[j]:\n",
    "                        return 2 + f(i+1, j-1)\n",
    "                    else:\n",
    "                        return max(f(i+1, j), f(i, j-1))\n",
    "        b = f(0, n-1)\n",
    "        if k>=(n-b):\n",
    "            return True \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     # 区间i,j 能否在k宽容度下成为palindrome\n",
    "        #     if j-i+1 <= k:\n",
    "        #         return True\n",
    "        #     elif k == -1:\n",
    "        #         return False\n",
    "            \n",
    "        #     if s[i] == s[j]:\n",
    "        #         return dfs(i+1,j-1,k)\n",
    "            \n",
    "        #     return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        # return dfs(0,n-1,k)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            # to make ij palindrome, minimal k\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j), dfs(i,j-1))+1\n",
    "        return dfs(0,n-1) <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i + 1, j - 1) + 2\n",
    "            return max(dfs(i + 1, j), dfs(i, j - 1))\n",
    "        return len(s) - dfs(0, n - 1) <= k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(l, r, c):\n",
    "            n = r - l + 1\n",
    "            if n == 1 or n == 2 and s[l] == s[r]: # 最后一段(最中间)\n",
    "                return True\n",
    "            if s[l] == s[r]:\n",
    "                return dfs(l+1, r-1, c)\n",
    "            elif c == 0: # 退格键已用完\n",
    "                return False\n",
    "            return dfs(l, r-1, c-1) or dfs(l+1, r, c-1)\n",
    "\n",
    "        return dfs(0, len(s)-1, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def isValid(left, right, k):\n",
    "            while left < right:\n",
    "                if s[left] == s[right]:\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    if k > 0:\n",
    "                        k -= 1\n",
    "                        return isValid(left+1, right, k) or isValid(left, right-1, k)\n",
    "                    else:\n",
    "                        return False\n",
    "            return True \n",
    "        return isValid(0, len(s)-1, k)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i,j,k):\n",
    "            # 区间i,j 能否在k宽容度下成为palindrome\n",
    "            if j-i+1 <= k:\n",
    "                return True\n",
    "            elif k == -1:\n",
    "                return False\n",
    "            \n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1,k)\n",
    "            \n",
    "            return dfs(i+1,j,k-1) or dfs(i,j-1,k-1)\n",
    "        return dfs(0,n-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(x, c):\n",
    "            n = len(x)\n",
    "            if n == 1 or n == 2 and x[0] == x[1]: # 最后一段(最中间)\n",
    "                return True\n",
    "            if x[0] == x[-1]:\n",
    "                return dfs(x[1:-1], c)\n",
    "            elif c == 0: # 退格键已用完\n",
    "                return False\n",
    "            return dfs(x[0:-1], c-1) or dfs(x[1:], c-1)\n",
    "            \n",
    "        return dfs(s, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidPalindrome(self, s: str, k: int) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(ss, kk):\n",
    "            if len(ss)==1 or (len(ss)==2 and ss[0]==ss[1]):\n",
    "                return True\n",
    "            if kk<=0 and ss[0]!=ss[-1]:\n",
    "                return False\n",
    "            if ss[0]==ss[-1]:\n",
    "                return dfs(ss[1:-1], kk)\n",
    "            else:\n",
    "                return dfs(ss[:-1], kk-1) or dfs(ss[1:], kk-1)\n",
    "\n",
    "\n",
    "        return dfs(s, k)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
